Modem digital computing systems often must allocate resources to requests for the resources. For instance, a data processor may issue three instructions each clock cycle. The same data processor may have, inter alia, two fixed point execution units and a single floating point execution unit. Therefore, the data processor cannot execute three fixed point instructions or three floating point instructions each clock cycle. The described data processor, in fact, may only execute up to two fixed point instructions or a single floating point instruction each clock cycle. Furthermore, it may be the case that one type of execution unit may not accept an instruction every cycle and, hence, is not always available. Some portion of the digital system must therefore be able to determine which execution unit performs which instruction.
Generally, the resources and requests are assigned an "order" within the digital computing system. This order implies that a first request is assigned to the first resource if the first request is requesting and the first resource is available. If the first request is requesting but the first resource is not available, then the first request will be assigned to the second resource if that resource is available. If the second resource is not available, then the first request will be assigned to the third resource, etc. Only after the first request is assigned to a resource or if the first request is initially not requesting will the second, third, etc. requests be allocated to the next available resource. Each request will be assigned to a resource after all previous requests have been assigned to a resource.
Known digital computing systems solve the resource allocation problem by incorporating one or more programmable logic arrays ("PLA") within them or by using general combinatorial logic. These approaches receive N inputs representative of various requests for resources and M inputs representative of the availability of each resource, where N and M are integers. The solutions generate an N.times.M output vector representative of which resource is allocated to which request.
In the three instructions per cycle example above, the digital computing system would require two PLAs. The first PLA would generate 6 outputs (3.times.2). This PLA would assign three requests for execution units to two fixed point execution units. The second PLA would generate 3 outputs (3.times.1). This PLA would assign three requests for execution units to a single floating point execution unit.
PLAs generate their output vector using a first level of AND gates driving a second level of OR gates. With only two levels of logic, PLAs are suitable for high speed applications. However, PLAs require an unacceptably large number of gates with as small a 4.times.4 or a 3.times.5 resource allocation problem. In addition, PLAs require a clock edge to synchronize their operation.
General combinatorial logic schemes generate vector outputs by using a large number of gates without the ordered structure of the PLA. The particular gate combination within a combinatorial logic solution is mathematically equivalent to the desired function.